In the field of computer graphics, the graphics rendering pipeline is the core of real time graphics. The main function of the pipeline is to generate, or render, a two dimensional image, given a virtual camera, three dimensional objects, light sources, lighting models, textures, and more. The locations and shapes of the objects in the scene are determined by their geometry, placement of camera in the environment and the characteristics of that environment. The appearance of the objects is affected by material properties, light sources, textures, and lighting models.
In general, texturing is a technique for efficiently modeling the surface properties of an object. Objects or models are normally represented graphically by triangles, as these are the geometric primitives used by most graphics hardware. Color for each vertex of the surface is computed using location of the light sources and the properties, position, and the normal of the vertex and the properties of the material belonging to the vertex. Thus, the color is computed by taking into account lighting and the material, as well as the viewer's position. Texturing works in modifying the values used in the lighting equation. The pipeline uses complex mathematical equations to blend the colors, textures and other inputs to create properly colored pixels in the image.
In prior art graphics systems a texture memory contains a two dimensional representation of a texture to be mapped onto primitives. Cache provides temporary storage of portions of texture memory for improved access speed. Graphic primitives are stored in a primitive storage portion of memory, and define the size and shape of graphic elements, such as triangles. Primitives are processed by triangle set up modules and traversed using edge walker modules and span walker modules. A texture mapping engine performs the operation of mapping textures stored in a texture memory onto primitives. Pixel processing is performed by 3D pipeline and performs operations on the pixels and writes the resulting rendered image via a render backend module to a frame buffer. The image in the frame buffer is sent to a display.
A primitive typically represents some element of a graphic image on a display screen, and a texture map contains some graphical pattern or image that is to be mapped onto the primitive image. The edge walker and span walker are typically used in the prior art to map texture images onto primitives. A number of different techniques are known in the prior art for scanning primitives. For example, spans of horizontal pixel rows are defined, and each span has a unique y value representing the pixel row. Each span has two edges of the primitives to limit the extent of the span. The primitive is traversed span by span and for each span the pixels within the span are processed in left to right order. A texel in a texture map corresponding to the selected pixel is retrieved. Data for the retrieved texel is rendered for the selective pixel in the primitive. Other pixels in the primitive are processed similarly. A check is performed to determine whether the end of the current span has been reached. This check may be performed, for example, by comparing the x coordinate of the currently selected pixel with the edge of the primitive. If the end of the span has not been reached, the span walker continues by selecting the next pixel and repeating texel retrieval. Operations such as burst mode and pixel walk vectors increase the efficiency of the operation.
U.S. Pat. No. 5,945,997 discloses a block and band oriented traversal and three dimensional triangle rendering. The disclosed system traverses and renders a graphic primitive by using block and band oriented traversal algorithms and texture mapping.
There is a need in the prior art to provide greater efficiency with a minimal amount of hardware for scanning primitives, and in particular, for texture mapping. All of the prior art methods attempt to find the edges of the primitive, by stepping outside the primitive as the pixels are edge walked or spanned.